package com.huangyi;

import java.util.Arrays;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 最长的斐波那契子序列的长度
    static class Solution {
        public int lenLongestFibSubseq(int[] arr) {
            int n = arr.length;
            // dp[i][j]: 以 arr[i] 和 arr[j] 结尾的斐波那契序列长度
            int[][] dp = new int[n][n];
            // 因为查询的是值（arr[j] - arr[i]），所以用哈希表加快搜索效率
            HashMap<Integer, Integer> hash = new HashMap<>();

            for (int[] x : dp) {
                // 初始化为 2，因为可能找不到前驱或前驱在中间，长度就是 2（不存在）
                Arrays.fill(x, 2);
            }
            for (int i = 0; i < n; i++) {
                hash.put(arr[i], i);  // 值 -> 索引
            }

            int ret = 2;
            for (int j = 2; j < n; j++) {
                for (int i = 1; i < j; i++) {
                    // 计算前驱元素的值，看哈希表是否存在
                    int target = arr[j] - arr[i];
                    if (target < arr[i] && hash.containsKey(target)) {
                        // 找到了！直接继承前面序列的长度 + 1
                        dp[i][j] = dp[hash.get(target)][i] + 1;
                    }
                    ret = Math.max(ret, dp[i][j]);
                }
            }
            return ret == 2 ? 0 : ret;  // 至少 3 个元素才算有效
        }
    }
}